package jm.data.structure.union_find;

/**
 * @Description QuickUnion 实现并查集
 * @date 2022/5/9 20:27
 */
public class QuickUnion extends AbstractUnionFind{

    public QuickUnion(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        rangeCheck(v);
        // 一直往上找 知道当前元素的父节点是自己就表示为根节点
        while (v != parents[v]){
            v = parents[v];
        }
        return v;
    }

    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;
        // 将当前节点的父节点改为要修改的节点的父节点
        parents[p1] = p2;
    }
}
